/**
 * 对数据不敏感，有序无序都是O(N^2)
 * 时间复杂度：O(N^2)
 * 空间复杂度：O(1)
 * 加了优化后，时间复杂度可能会变成O(N),只走一次就有序了
 * 稳定性：稳定
 * 稳定的排序有 ： 冒泡  插入  归并
 */

public class BubbleSort {

    public static void bubbleSort(int[] array) {
        boolean flag = false;
        for(int i = 0; i < array.length - 1; i++) {
            for(int j = 0; j < array.length - i - 1; j++) {
                if(array[j] > array[j+1]) {
                    Swap(array,j,j+1);
                    flag = true;
                }
            }
            if(!flag) {
                break;
            }
        }
    }

    public static void Swap(int[] array,int x,int y) {
        int tmp = array[x];
        array[x] = array[y];
        array[y] = tmp;
    }

}
